Best-first search is a form of tree search where there is a heuristic evaluation for each node. The best-first algorithm maintains an open list of all the nodes it has not yet explored and at each step chooses the node with the best heuristic to follow down the tree, only backtracking when it gets to a leaf node, or in some other way reaches an impasse. However, when it backtracks ot considers the whole open list, unlike hill climbing with backtracking, which only steps back to the most recent choice.
Used in Chap. 4: pages 48, 49, 50, 55
Also known as best first, best first
Tree with goal leaf nodes marked with a tick, non-goal leaves marked with a cross, and heuristic values in brackets (small is better). Hill climbing with backtracking will consider the nodes in the order a, b, c, f, j, then realise that j is not a goal so backtrack to the last decision point at c and then follow g, l to get to a feasible but not optimal state. In contrast, best first search considers all nodes in the open list at each point, so at state f considers the nodes ( j[99], g[4], b[3] ), and so follows the c branch down to h a better solution (although still not guaranteed to be optimal depending on the properties of the heuristic).